package com.cqs.leetcode.string;

import org.apache.commons.io.FileUtils;

import java.io.File;
import java.io.IOException;
import java.util.*;
import java.util.function.Function;

/**
 * @author lixiaowen
 * @create 2019-12-25
 */
public class GroupAnagrams49 {

    static class Solution {

        public List<List<String>> groupAnagrams(String[] strs) {
            //归并集
            List<List<String>> lists = new ArrayList<>();
            if (strs == null || strs.length == 0) return lists;
            lists.add(new ArrayList<String>() {{
                this.add(strs[0]);
            }});
            for (int i = 1; i < strs.length; i++) {
                String str = strs[i];
                int size = lists.size();
                boolean find = false;
                for (int j = 0; j < size; j++) {
                    List<String> group = lists.get(j);
                    String anagram = group.get(0);
                    if (isAnagrams(anagram, str)) {
                        group.add(str);
                        find = true;
                        break;
                    }
                }
                if (!find) {
                    lists.add(new ArrayList<String>() {{
                        add(str);
                    }});
                }
            }
            return lists;
        }

        private boolean isAnagrams(String s1, String s2) {
            if (s1.length() != s2.length()) return false;
            Function<String, Map<Character, Integer>> func = s -> {
                Map<Character, Integer> map = new HashMap<>();
                char[] chars = s.toCharArray();
                for (char c : chars) {
                    map.put(c, map.getOrDefault(c, 0) + 1);
                }
                return map;
            };
            Map<Character, Integer> map1 = func.apply(s1);
            Map<Character, Integer> map2 = func.apply(s2);
            if (map1.size() != map2.size()) return false;
            for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
                if (!map2.getOrDefault(entry.getKey(), 0).equals(entry.getValue())) return false;
            }
            return true;
        }

    }

    static class Solution1 {

        public List<List<String>> groupAnagrams(String[] strs) {
            Map<String, List<String>> map = new HashMap<>();
            if (strs == null || strs.length == 0) return new ArrayList<>(map.values());
            for (int i = 0; i < strs.length; i++) {
                String str = strs[i];
                char[] chars = str.toCharArray();
                Arrays.sort(chars);
                String key = new String(chars);
                List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
                list.add(str);
            }
            return new ArrayList<>(map.values());
        }
    }

    static class Solution2 {

        public List<List<String>> groupAnagrams(String[] strs) {
            Map<String, List<String>> map = new HashMap<>();
            if (strs == null || strs.length == 0) return new ArrayList<>(map.values());
            Function<String, String> func = str -> {
                int[] count = new int[26];
                char[] chars = str.toCharArray();
                StringBuilder sb = new StringBuilder();
                for (char c : chars) {
                    count[c - 'a']++;
                }
                for (int i = 0; i < count.length ; i++) {
                    sb.append(count[i]);
                    sb.append('#');
                }
                return sb.toString();
            };
            for (String str : strs) {
                String key = func.apply(str);
                List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
                list.add(str);
            }
            return new ArrayList<>(map.values());
        }
    }


    public static void main(String[] args) throws IOException {
//        Solution1 solution = new Solution1();
        Solution2 solution = new Solution2();
        String[] testCase = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<String> list = FileUtils.readLines(new File("src/main/java/com/cqs/leetcode/testCases/testCase49.txt"));
        Function<String, String[]> func = new Function<String, String[]>() {
            @Override
            public String[] apply(String s) {
                s = s.replaceAll("]|\\[|\\\"", "");
                return s.split(",");
            }
        };

        List<List<String>> lists = solution.groupAnagrams(testCase);
        System.out.println(lists);
        long l = System.currentTimeMillis();
        for (String s : list) {
            testCase = func.apply(s);
            lists = solution.groupAnagrams(testCase);
            // System.out.println(lists);

        }
        System.out.println(System.currentTimeMillis() - l + "毫秒");
    }
}
